package solutions.leetcode.easy;

import solutions.lib.BaseSolution;

import java.util.*;

/**
 * @author lizhidong
 * <a href="https://leetcode-cn.com/problems/next-greater-element-i/">496. 下一个更大元素 I</a>
 */
public class Solution496 extends BaseSolution {

    public int[] nextGreaterElement(int[] nums1, int[] nums2) {
        Map<Integer, Integer> map = new HashMap<>();
        int[] stack = new int[nums2.length];
        int si = -1;

        int p = nums2.length - 1;
        while (p >= 0) {
            while (si >= 0) {
                if (nums2[p] < stack[si]) {
                    map.put(nums2[p], stack[si]);
                    stack[++si] = nums2[p];
                    break;
                } else {
                    si--;
                }
            }
            if (si < 0) {
                stack[++si] = nums2[p];
                map.put(nums2[p], -1);
            }
            p--;
        }
        for (int i = 0; i < nums1.length; i++) {
            nums1[i] = map.get(nums1[i]);
        }
        return nums1;
    }

    public static void main(String[] args) {
        Solution496 solution = new Solution496();
        printVals(solution.nextGreaterElement(new int[] {
                2, 4
        }, new int[] {
                1,2,3,4
        }));
    }
}